package algorithm.swordoff;

/**
 * 正则表达式匹配
 */

public class SQ19 {

    public boolean isMatch(String s, String p) {
        // dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if (i == 0 && j == 0) dp[i][j] = true;

                // 这行不能漏,一定是偶数索引才可能是true,考虑a(a*)是不可能匹配空字符串的而(a*)则可以
                else if (i == 0 && (j&1) == 0) dp[i][j] = dp[i][j - 2] && p.charAt(j - 1) == '*';

                else if (i > 0 && j > 0) {
                    // 根据模式串p的j-1情况分类

                    // 情况1:是点,必须s.charAt(i-1)匹配p.charAt(j-1)
                    if (p.charAt(j-1) == '.') dp[i][j] = dp[i-1][j-1];
                    // 情况2:是*,需要根据p.charAt(j-2)来判断,此时p.charAt(j-2)有两种情况是点,或者正常字符(因为两个*不可能连在一起)
                    else if (p.charAt(j-1) == '*') {
                        // 第一种情况:pj-2pj-1匹配0次,那么就看dp[i][j-2]
                        // 第二种情况:pj-2pj-1匹配0次以上,这里面还要分两种情况
                        // 2-1:pj-2是字母,看下子结构:s的去掉最后一个字母能不能匹配 并且 s去掉的这个字母和p的*前面的一个字母是不是一样
                        // 2-2:pj-2是点,看下子结构:s的去掉最后一个字母能不能匹配
                        dp[i][j] = dp[i][j-2] || (dp[i-1][j] && s.charAt(i-1) == p.charAt(j-2)) || (dp[i-1][j] && p.charAt(j-2) == '.');
                    }
                    // 情况3:是正常字符,必须s.charAt(i-1)匹配p.charAt(j-1)
                    else dp[i][j] = dp[i-1][j-1] && s.charAt(i-1) == p.charAt(j-1);
                }
            }
        }
        return dp[s.length()][p.length()];
    }


    public static void main(String[] args) {
        SQ19 sq19 = new SQ19();
        sq19.isMatch("aa", "a*");
    }
}
